/**
 * @fileOverview what is this file for?
 * @author Xaephis <xaephis@gmail.com>
 * @version v 2.69 Tue Jun 07 2011 06:04:27 GMT+0800 (China Standard Time)
 */

Jx.declare('Jx.lib.Parser', {

	$requires: [

		'Jx.lib.Lexeme',

		'Jx.lib.Tokenizer'

	],

	tokenizer: 'Jx.lib.Tokenizer',

	Lexeme: 'Jx.lib.Lexeme',

	bufferAnchors: undefined,

	buffer: undefined,

	tokens: undefined,

	state: 'start',

	endState: 'end',

	states: {

		'start': {}

	},

	reduceStates: {},

	anchors: [],

	anchorIndexes: undefined,

	anchoredReductions: undefined,

	failed: false,

	completed: false,

	tokenCursor: 0,

	ignoreProductions: [],

	constructor: function(){

		this.initializeTokenizer(this.tokenizer);

		this.bufferAnchors = [];

		this.buffer = [];

		this.tokens = [];

		this.initializeAnchors(this.anchors);

		this.initializeIgnoredProductions(this.ignoreProductions);

		this.$super();

	},

	initializeTokenizer: function(tokenizer){

		if (Jx.isString(tokenizer, true) &&

			Jx.classExists(tokenizer)

		){

			tokenizer = Jx.isSingleton(tokenizer) ?

				Jx.getClass(tokenizer)

				:

				Jx.instantiate(tokenizer);

		}

		if (Jx.instanceOf(tokenizer, 'Jx.lib.Tokenizer')){

			this.tokenizer = tokenizer;

		} else {

			throw Jx.createError('invalid tokenizer [', tokenizer, '] for parser');

		}

	},

	initializeIgnoredProductions: function(productions){

		var listIndex = this.ignoreProductions;

		if (Jx.isArray(listIndex)){

			listIndex = this.ignoreProductions = {};

			for(var l=productions.length, p; l--;){

				if (Jx.isString(p = productions[l], true)){

					listIndex[p] = true;

				}

			}

		}

	},

	initializeAnchors: function(anchors){

		var indexes = this.anchorIndexes,

			reductions = this.anchoredReductions,

			anchor;

		if (!Jx.isObject(indexes)){

			this.constructor.override({

				anchorIndexes: indexes = {},

				anchoredReductions: reductions = {}

			});

			for(var l=anchors.length; l--;){

				anchor = anchors[l];

				reductions[anchor] = true;

				indexes[

					anchor.substring(0, anchor.lastIndexOf(':'))

				] = true;

			}

		}

	},

	getTokenAt: function(at){

		var tokens = this.tokens,

			tokenizer = this.tokenizer,

			found, c;

		if (Jx.isNumber(at)){

			c = tokens.length;

			for(var c = tokens.length; c<=at; c++){

				this.getNextToken();

			}

			found = tokens.hasOwnProperty(at) ?

				tokens[at]

				:

				null;

		}

		return found;

	},

	getNextToken: function(){

		var tokens = this.tokens,

			tokenizer = this.tokenizer,

			ignoreList = this.ignoreProductions,

			found, end;



		while(!end){

			found = tokenizer.next();

			if (!found || !ignoreList.hasOwnProperty(found.token)){

				end = true;

				if (found){

					tokens.push(found);

				}

			}

		}

		return found;


	},

	getNextState: function(current, production){

		var s = this.states,

			o = s.hasOwnProperty(current) ?

				s[current]

				:

				null;

		return o && o.hasOwnProperty(production) ?

			o[production]

			:

			null;

	},

	getLastReducableLexemeIndex: function(at){

		var buffer = this.buffer,

			l = Jx.isNumber(at) && at >= 0 && at <= (buffer.length - 1) ?

				at + 1

				:

				buffer.length;

		for(; l--;){

			if (buffer[l].reduceProduction){

				return l;

			}

		}

		return -1;

	},

	setupFoundState: function(production, current, nextState, bufferIndex){

		var buffer = this.buffer,

			reductions = this.reduceStates,

			bufferAnchors = this.bufferAnchors,

			anchorIndexes = this.anchorIndexes,

			anchorName = current+':'+nextState,

			reduceRef = current in reductions ?

				reductions[current]

				:

				null;

		//-- check anchors
		if (anchorIndexes.hasOwnProperty(anchorName)){

			bufferAnchors[bufferAnchors.length] = {

				index: bufferIndex,

				name: anchorName,

				state: current

			};

		}


		if (reduceRef && reduceRef.hasOwnProperty(production)){

			buffer[bufferIndex].reduceProduction = reduceRef[production];

		}

	},

	appendBuffer: function(token){

		var lexeme = this.createLexemeFromToken(token),

			buffer = this.buffer;

		buffer[buffer.length] = lexeme;

		return lexeme;

	},

	createLexeme: function(production, value, rangeFrom, rangeTo, terminal){

		var lexeme = Jx.instantiate(this.Lexeme);

		lexeme.parser = this;

		lexeme.production = production;

		lexeme.value = value;

		lexeme.range = [rangeFrom, rangeTo];

		lexeme.terminal = terminal !== false;

		return lexeme;

	},

	createLexemeFromToken: function(token, state){

		var lexeme = this.createLexeme(token.token, token.value, token.from, token.to + 1);

		lexeme.state = state;

		return lexeme;

	},

	reduce: function(callback, scope){

		var buffer = this.buffer,

			bufferAnchors = this.bufferAnchors,

			anchoredReductions = this.anchoredReductions,

			ret = void(0),

			anchor, production,

			anchorIndex, reduceIndex, lexeme;

		while(bufferAnchors.length){

			anchor = bufferAnchors.pop();

			anchorIndex = anchor.index;

			reduceIndex = this.getLastReducableLexemeIndex();

			//-- reduce
			if (reduceIndex != -1 && reduceIndex >= anchorIndex){

				production = buffer[reduceIndex].reduceProduction;

				//-- check if it can reduce
				if (anchor.name+':'+production in anchoredReductions){

					lexeme = this.reduceToBuffer(production, anchorIndex, reduceIndex + 1);

					lexeme.state = anchor.state;

					//-- call
					if (callback.call(scope, lexeme.production, lexeme) !== false){

						ret = {

							lexeme: lexeme,

							state: anchor.state,

							index: anchorIndex

						}

					}

					break;

				//-- this anchor is not reducable, try next anchor
				} else {

					continue;

				}

			//-- reduction failed!
			} else {

				break;

			}

		}

		return ret;

	},

	next: function(callback, scope){

		scope = scope || window;

		var state = this.state,

			buffer = this.buffer,

			bufferAnchors = this.bufferAnchors,

			stateIndexes = this.states,

			ended = false,

			lexeme, lexemeState,

			reduced,

			token, bufferIndex,

			ret;

		if (!this.failed && !this.completed){

			token = this.getNextToken();

			if (token === false){

				this.failed = true;

			} else if (token){

				lexeme = this.appendBuffer(token);

				lexeme.state = state;

				bufferIndex = buffer.length - 1;

				while(!ended){

					lexemeState = this.getNextState(state, lexeme.production);

					if (lexemeState){

						this.setupFoundState(lexeme.production, state, lexemeState, bufferIndex);

						bufferIndex++;

						if (bufferIndex < buffer.length){

							lexeme = buffer[bufferIndex];

							state = lexemeState;

						}

					//-- try reducing
					} else if (bufferAnchors.length){

						reduced = this.reduce(callback, scope);

						if (reduced){

							lexeme = reduced.lexeme;

							lexeme.state = state = reduced.state;

							bufferIndex = reduced.index;

						} else {

							break;

						}

					} else {

						break;

					}

					if (bufferIndex == buffer.length){

						ended = true;

						this.state = lexemeState;

						ret = lexeme;

					}

				}

			}

			if (ret && this.state == this.endState){

				reduced = this.reduce(callback, scope);

				if (reduced && !bufferAnchors.length && buffer.length == 1){

					ret = reduced.lexeme;

					this.completed = true;

				} else {

					this.failed = true;

				}

			} else if (!ret){

				this.failed = true;

			}

		}

		return ret;


	},



	parse: function(input, callback, scope){

		scope = Jx.isNumber(scope) || scope ? scope : null;

		var buffer = this.buffer,

			result, ret;

		this.reset();

		this.tokenizer.set(input);

		while(!this.completed && !this.failed){

			this.next(callback, scope);

		}

		if (!this.failed && buffer.length){

			ret = buffer[0];

		}

		return ret;

	},

	reset: function(){

		this.bufferAnchors = [];

		this.buffer = [];

		this.tokens = [];

		delete this.state;

		delete this.failed;

		delete this.completed;

	},

	reduceToBuffer: function(production, index, end){

		var buffer = this.buffer,

			values = buffer.splice(index, end - index),

			lexeme = this.createLexeme(production, values, values[0].range[0], values[values.length - 1].range[1], false);

		//-- replace!
		buffer.splice(index, 0, lexeme);

		return lexeme;

	}





});
